package com.itcam.otcbackend.demo;

import java.util.concurrent.ThreadLocalRandom;

import static cn.hutool.core.util.ArrayUtil.swap;
import static com.itcam.otcbackend.demo.QuickSort.quickSort;

/**
 * @author : Cammy.Wu
 * Description : 
 */

public class DoubleQuickSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1};
        doubleQuickSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    private static void doubleQuickSort(int[] nums) {
        int n = nums.length;
        quickSort(nums, 0, n - 1);
    }

    private static void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(nums, left, right);
        quickSort(nums, left, p - 1);
        quickSort(nums, p + 1, right);
    }

    private static int partition(int[] nums, int left, int right) {
        int index = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        swap(nums, index, right);
        int pv = nums[left];
        int x = left + 1;
        int y = right;
        while (true) {
            while (x <= y && nums[x] <= pv) {
                x++;
            }
            while (x <= y && nums[y] >= pv) {
                y--;
            }
            if (x > y) {
                break;
            }
            swap(nums, x, y);
            x++;
            y--;
        }
        swap(nums, left, y);
        return y;
    }
}
